package com.example.link;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @Date 2022/3/6
 * @Created by Jonathan
 */
public class CopyLinkedListWithRand {
    private static class Node {
        private int value;
        private Node next;
        private Node rand; // rand指针


        public Node(int value) {
            this.value = value;
        }
    }

    private static Node create(List<Integer> list) {
        Node head = new Node(list.get(0));
        Node cur = head;
        for (int i = 1; i < list.size(); i++) {
            cur.next = new Node(list.get(i));
            cur = cur.next;
        }
        return head;
    }

    /**
     * 打印链表
     *
     * @param head 头结点
     */
    private static void print(Node head) {
        Node cur = head;
        while (cur != null) {
            System.out.printf("%d ", cur.value);
            cur = cur.next;
        }
        System.out.print("\n");
    }

    @Test
    public void testCreate() {
        List<Integer> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        Node node = create(list);
        copyRandList(node);

    }

    private static void copyRandList(Node head) {
        // 先赋值链表
        Node cur = head;
        while (cur != null) {
            // 复制当前节点
            Node next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            // 移动指针
            cur = cur.next.next;
        }
        System.out.println("合在一起的链表：");
        print(head);
        // 复制rand指针
        cur = head;
        while (cur != null) {
            Node rand = cur.rand;
            Node copy = cur.next;
            // 优化成三元表达式
            if (rand == null)
                copy.rand = null;
            else
                copy.rand = rand.next;
            cur = cur.next.next;
        }
        // 将赋值的节点给提出来
        System.out.println("合在一起的链表：");
        print(head);
        cur = head;
        Node newHead = null, newTail = null;
        while (cur != null) {
            Node copy = cur.next;
            if (newHead == null) {
                newHead = newTail = copy;
            } else {
                newTail.next = copy;
                newTail = newTail.next;
            }
            // 这个地方应该改指针 而不光是指向
            // cur = cur.next.next; // 不改指针 就这么写的话 第一个节点的指针有问题
            cur.next = copy.next;
            cur = cur.next;
        }
        System.out.println("新的链表:");
        print(newHead);
        System.out.println("原来的链表:");
        print(head);
    }


}
